import java.util.Arrays;
import java.util.HashMap;

/**
 * 给你 k 种面值的硬币，面值分别为 c1, c2 ... ck，每种硬币的数量无限，再给一个总金额 amount，问你最少需要几枚硬币凑出这个金额，如果不可能凑出，算法返回 -1
 */
class CoinChange {

    public static void main(String[] args) {
        // System.out.println(CoinChange.coinChange(new int[]{1, 2, 3, 5}, 12));
        System.out.println(CoinChange.coinChange1(new int[]{2}, 3));
    }

    /**
     * 自上而下的递归，没有优化，很慢
     * @param coins
     * @param amount
     * @return
     */
    public static int coinChange1(int[] coins, int amount) {
        if (amount == 0) return 0;
        if (amount < 0) return -1;
        int res = Integer.MAX_VALUE;
        for (int coin : coins) {
            int sub = coinChange2(coins, amount - coin);
            if (sub < 0) continue;
            res = min(res, sub + 1);
        }
        if (res != Integer.MAX_VALUE) {
            return res;
        } else { ;
            return -1;
        }
    }

    public static int min(int a, int b) {
        return a < b ? a : b;
    }

    public static int coinChange2(int[] coins, int amount) {
        HashMap<Integer, Integer> map = new HashMap();
        return coinChangeWithMap(coins, amount, map);
    }

    /**
     * 使用了备忘录的递归，减少重复运算
     *
     * @param coins
     * @param amount
     * @param map
     * @return
     */
    public static int coinChangeWithMap(int[] coins, int amount, HashMap<Integer, Integer> map) {
        if (amount == 0) return 0;
        if (amount < 0) return -1;
        if (map.containsKey(amount)) return map.get(amount);
        int res = Integer.MAX_VALUE;
        for (int coin : coins) {
            int sub = coinChangeWithMap(coins, amount - coin, map);
            if (sub < 0) continue;
            res = min(res, sub + 1);
        }
        if (res != Integer.MAX_VALUE) {
            map.put(amount, res);
            return res;
        } else {
            map.put(amount, -1);
            return -1;
        }
    }

    /**
     * 自下而上的递归,情况最少
     *
     * @param coins
     * @param amount
     * @return
     */
    public static int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;
        for (int i = 0; i < dp.length; i++) {
            for (int coin : coins) {
                if (i - coin < 0) continue;
                dp[i] = min(dp[i], 1 + dp[i - coin]);
            }
        }
        return dp[amount] == amount + 1 ? -1 : dp[amount];
    }


}